//class Solution {
//public:
//    // 非递归实现方法
//    vector<int> postorderTraversal(TreeNode* root) {
//        stack<TreeNode*> st;
//        vector<int> v;
//        TreeNode* prev = nullptr;
//
//        TreeNode* cur = root;
//        while (cur || !st.empty())
//        {
//            while (cur)
//            {
//                st.push(cur);
//                cur = cur->left;
//            }
//
//            TreeNode* top = st.top();
//            //v.push_back(top->val);
//            //st.pop();
//
//            if (top->right == nullptr || top->right == prev)
//            {
//                st.pop();
//                v.push_back(top->val);
//                prev = top;
//            }
//            else
//            {
//                cur = top->right;
//            }
//        }
//
//        return v;
//    }
//};
        
    
//class Solution {
//public:
//
//    TreeNode* link(vector<int>& pv, vector<int>& iv, int l, int r, int& index)
//    {
//        if (l > r)
//        {
//            return nullptr;
//        }
//
//        int nodeval = pv[index];
//        TreeNode* cur = new TreeNode(pv[index ++ ]);
//
//        int k;
//        for (k = l; k <= r; k ++ )
//        {
//            if (nodeval == iv[k])
//            {
//                break;
//            }
//        }
//
//        cur->left = link(pv, iv, l, k - 1, index);
//        cur->right = link(pv, iv, k + 1, r, index);
//
//        return cur;
//    }
//
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//        if (preorder.empty())
//            return nullptr;
//        int i = 0;
//        TreeNode* root = link(preorder, inorder, 0, preorder.size() - 1, i);
//
//        return root;
//    }
//};

//class Solution {
//public:
//
//	void link(TreeNode* cur, TreeNode*& prev)
//	{
//		if (cur == nullptr)
//		{
//			return;
//		}
//
//		link(cur->left, prev);
//
//		if (prev != nullptr)
//		{
//			cur->left = prev;
//			prev->right = cur;
//		}
//		prev = cur;
//
//		link(cur->right, prev);
//	}
//
//    TreeNode* Convert(TreeNode* pRootOfTree) {
//        if (pRootOfTree == nullptr)
//		{
//			return nullptr;
//		}
//
//		TreeNode* prev = nullptr;
//
//		link(pRootOfTree, prev);
//
//		while (pRootOfTree->left != nullptr)
//		{
//			pRootOfTree = pRootOfTree->left;
//		}
//
//		return pRootOfTree;
//    }
//};
//
